package Atop100.listNode;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class LRUcacheDemo {

    public static void main(String[] args) {
        LRUCache lruCache = new LRUcacheDemo().new LRUCache(3);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.put(3,3);
        lruCache.put(4,2);
//        lruCache.put(3,5);
        Set<Map.Entry<Integer, Node<Integer, Integer>>> entries = lruCache.map.entrySet();
        Iterator<Map.Entry<Integer, Node<Integer, Integer>>> iterator = entries.iterator();
        while (iterator.hasNext()){
            Map.Entry<Integer, Node<Integer, Integer>> next = iterator.next();
            System.out.println(next.getKey()+"  "+next.getValue().value);
        }

    }


    class  Node<K,V>{
        K key;
        V value;
        Node<K,V> pre;
        Node<K,V> next;

        public  Node(){
            this.pre=this.next=null;
        }

        public  Node(K key,V value){
            this.key=key;
            this.value=value;
            this.pre=this.next=null;
        }


    }

    class DoubleLinkedList<K,V>{
        Node<K,V> head;
        Node<K,V> tail;

        public   DoubleLinkedList(){
            head=new Node<>();
            tail=new Node<>();
            head.next=tail;
            tail.pre=head;
        }

        public  void  addHead(Node<K,V> node){
            node.next=head.next;
            node.pre=head;
            //TODO:2023/10/28  这两个的顺序不能颠倒
            head.next.pre=node;
            head.next=node;

        }


        public void  removeNode(Node<K,V> node){
            node.pre.next=node.next;
            node.next.pre=node.pre;
            //TODO:2023/10/28 node 自身的处理
            node.next=null;
            node.pre=null;
        }
        //TODO:2023/10/28  要这个的作用是当 lru满额时候好进行删除
        public  Node  getLast(){
            return  tail.pre;
        }

    }


    class LRUCache {
        private  int  capacity;
        Map<Integer,Node<Integer,Integer>> map;
        DoubleLinkedList<Integer,Integer> doubleLinkedList;

        public LRUCache(int capacity) {
            this.map=new HashMap<>();
            this.capacity=capacity;
            this.doubleLinkedList=new DoubleLinkedList<>();
        }

        public int get(int key) {
            if (!map.containsKey(key)){
                return  -1;
            }
            Node<Integer, Integer> integerIntegerNode = map.get(key);
            doubleLinkedList.removeNode(integerIntegerNode);
            doubleLinkedList.addHead(integerIntegerNode);
            return integerIntegerNode.value;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)){
                Node<Integer, Integer> node = map.get(key);
                node.value=value;
                map.put(key,node);
                doubleLinkedList.removeNode(node);
                doubleLinkedList.addHead(node);
            }else {
                if (map.size()==capacity){
                    Node last = doubleLinkedList.getLast();
                    doubleLinkedList.removeNode(last);
                    map.remove(last.key);
                }
                Node<Integer, Integer> newNode = new Node<>(key, value);
                map.put(key,newNode);
                doubleLinkedList.addHead(newNode);


            }

        }
    }

}


